Memory is generally allocated for a program during execution from a pool of unused memory area called a heap. Garbage collection is a form of memory management for programs. During execution, the garbage collector attempts to identify memory allocated to objects that are not in use by the program, so that they may be deallocated, or reclaimed. An object may be in use by the program, or reachable, if the object can be accessed or reached by the program's current state. Since the precise allocation of space in the heap to objects is not known in advance, the memory allocated to objects cannot be accessed via the actual address of the memory. Rather, the memory may be accessed indirectly by the program utilizing references. An object is reachable if it is referenced by a local variable or parameter in a currently invoked function or a global variable, or is referenced by a reachable object. The garbage collector deallocates memory allocated to objects that are no longer reachable. It must not deallocate memory occupied by objects that are still reachable.
One kind of garbage collector, referred to herein as a Garbage-first garbage collector, is a generational, region-based garbage collector whose strategy is to minimize garbage collection copying time by identifying regions with the most garbage for collection. A generational garbage collector divides objects into generations and collects younger generations more frequently than older generations. An example of a generational garbage collector is described in the article “Generation Scavenging: A Non-Disruptive High Performance Storage Reclamation Algorithm,” David Ungar, SIGPLAN Notices, 19(5):157-167, May 1984. A region-based garbage collector divides the heap into regions and collects sets of regions during garbage collection. An example of a region-based garbage collector is described in the article “Incremental Collection of Mature Objects,” Richard L Hudson and J. Eliot B. Moss, In Yves Bekkers and Jacques Cohen, editors, International Workshop on Memory Management, Lecture Notes in Computer Science, pages 388-403, St. Malo, France, September 1992. The Garbage-first garbage collector performs frequent garbage collections where the garbage collector deallocates memory allocated to objects that are no longer reachable and less frequent marking cycles where the garbage collector marks reachable objects.
The Garbage-first garbage collector divides the heap space into “Young” regions, “Old” regions and “Humongous” regions. Objects stored in the various regions are referred to as Young, Old, or Humongous depending on the corresponding region in which they are stored. When objects are first allocated memory, they are generally designated as Young objects and stored in a Young region. Eventually Young objects are “promoted” to storage in Old regions if they are not deallocated previous to that point. Humongous regions may be utilized to store objects that are significantly larger than the typical object size, referred to as “Humongous” objects. Objects may be designated as Humongous and stored in Humongous regions if their size is above a threshold, such as above fifty percent of the size of a region. Humongous objects may be designated as Humongous objects when allocated rather than as Young objects. Thusly, Humongous objects will never be stored in Young regions. Generally, a Humongous region only stores one object, though it may only store part of an object that is too large to fit in one region. In such a case, a single Humongous object may be stored across multiple Humongous regions.
The Garbage-first garbage collector treats objects that are designated as Young objects differently from objects that are designated as Old objects on the assumption that most objects can be deallocated within a short period of time after allocation. Based on this assumption, the Garbage-first garbage collector attempts to collect Young regions more frequently than Old regions in hopes of reclaiming a maximum amount of heap space for a minimum amount of garbage collection work. The Garbage-first garbage collector may attempt to collect all Young regions every time it performs a collection but may attempt to collect Old regions only part of the time that it performs collections and may only reclaim Humongous regions at the end of marking cycles when they do not contain any marked objects.
For example, the Garbage-first garbage collector may perform a marking cycle upon a triggering event, such as when seventy percent of the heap has been allocated. The garbage collector marks all reachable objects and uses the marking information to create a “marking cycle list” of Old regions, ranked by garbage collection efficiency, to attempt to collect the next time a collection is performed. At the end of a marking cycle, the garbage collector also reclaims any Old regions or Humongous regions that do not contain any marked objects. If a garbage collection occurs after a marking cycle has been performed and worthwhile Old regions remain on the marking cycle list, the garbage collector may collect all Young regions and a number of Old regions on the marking cycle list. If a garbage collection occurs previous to the performance of a marking cycle and/or if no worthwhile Old regions remain on the marking cycle list, the garbage collector may only collect Young regions.
Further, the Garbage-first garbage collector processes Humongous regions differently from Young regions and Old regions. For example, when collecting Young regions and Old regions, the Garbage-first garbage collector copies reachable objects from the region being collected to a different region and then the entire region being collected is reclaimed. When processing Humongous regions, Humongous objects are not copied. Rather, if the Humongous object or partial Humongous object stored in the Humongous region is reachable, the Humongous region is left in place. However, if the Humongous object or partial Humongous object stored in the Humongous region is not reachable, the Humongous region is directly reclaimed without any copying to a different region.
Thus, the Garbage-first garbage collector typically spends a small amount of garbage collection time processing Humongous regions in relation to the amount of heap space that may potentially be reclaimed. This is in part due to the fact that the garbage collector is only required to determine whether one object is reachable when the garbage collector collects a Humongous region. The ratio between the amount of heap space that may be reclaimed and the amount of garbage collection time spent by the Garbage-first garbage collector may be increased through more frequent processing of Humongous regions.